package com.tree.rbt;

import java.util.Scanner;

/**
 * 红黑树条件：
 * 1、结点只有红色和黑色
 * 2、根结点为黑色
 * 3、叶子结点（NIL）结点是黑色
 * 4、红色结点不能相连即是红色结点的两个子节点都是黑色结点
 * 5、从根结点到叶子结点的路径上，黑色结点的数量相同
 * <p>
 * 从条件4和条件5，说明了红黑树中最长路径是最短路径长度的两倍，本质上也是通过树高来控制平衡的，红黑树比AVL树树高的控制条件更松散，红黑树
 * 调整发生在结点插入和删除之后，发生调整的概率比AVL树更小
 * <p>
 * 调整策略：
 * 1、插入调整站在祖父节点看
 * 2、删除调整站在父节点看
 * 3、插入和删除的情况处理一共5种
 * 插入调整：
 * 情况1：叔叔节点是红色
 *      直接把祖父节点变为红色，父节点和叔叔节点变为黑色
 * 情况2：叔叔节点是黑色或者NIL节点
 *      1.插入节点在祖父节点的右侧，父节点的右侧，祖父节点左旋，父节点变为黑色，父节点的两个子节点变为红色；或者父节点变为红色，两个子节点变为黑色
 *      2.插入节点在祖父节点的右侧，父节点的左侧，对父节点进行小右旋，转换为情况2.1进行处理
 *      3.插入节点在祖父节点的左侧，父节点的左侧，祖父节点右旋。父节点变为黑色，父节点的两个子节点变为红色；或者父节点变为红色，两个子节点变为黑色
 *      4.插入节点在祖父节点的左侧，父节点的右侧，对父节点进行小左旋，转换为情况2.3进行处理
 *
 *
 * 删除调整发生的前提
 * 1、删除红色结点，不会对红黑树的平衡产生影响
 * 2、度为1的黑色结点，其唯一子孩子一定是红色
 * 3、删除度为1的黑色结点，不会产生删除调整
 * 4、删除度为0的黑色结点，会产生一个双黑的NIL结点
 * 5、删除调整主要就是为了处理双黑的情况
 *
 * 情况1：双黑结点的兄弟结点是黑色，兄弟结点下的两个子节点也是黑色
 *      双黑结点和兄弟结点黑色减一，父节点黑色加1
 * 情况2：双黑结点的兄弟结点是黑色且兄弟结点的孩子结点中有红色结点
 *      1.兄弟结点在右（R），兄弟结点的右子节点是红色（R）
 *          对父节点进行左旋，新根结点（原兄弟结点）颜色变为原根结点（现左子节点）颜色，新根结点的左右子节点颜色变为黑色，双黑结点黑色减1
 *      2.兄弟结点在右（R），兄弟结点的左子节点是红色（L）
 *          对兄弟结点进行小右旋，新根结点（原兄弟结点的左子节点）与原根结点（原兄弟结点）颜色互换，情况转换为2.1，根据2.1情况进行继续处理
 *      3.兄弟结点在左（L），兄弟结点的左子节点是红色（L）
 *          对父节点进行右旋，新根结点（原兄弟结点）颜色变为原根结点（先右子节点）颜色，新根结点的左右子节点颜色变为黑色，双黑结点黑色减1
 *      4.兄弟结点在左（L），兄弟结点的右子节点是红色（R）
 *          对兄弟结点进行小左旋，新根结点（原兄弟结点的右子节点）与原根结点（原兄弟结点）颜色互换，情况转换为2.3，根据2.3情况进行继续处理
 * 情况3：双黑结点的兄弟结点是红色
 *      旋转父节点，转变为现兄弟结点是黑色，跳转到情况2里面进行处理
 * @author rkc
 * @date 2021/7/17 8:50
 */
public class RedBlackTree {

    private static final int RED = 0;
    private static final int BLACK = 1;
    private static final int DOUBLE_BLACK = 2;
    private static final Node NIL = initNilNode();

    public static class Node {
        private int key;
        private Node leftChild;
        private Node rightChild;
        private int color;
    }

    public static Node createNode(int key) {
        Node node = new Node();
        node.key = key;
        node.color = RED;
        node.leftChild = node.rightChild = NIL;
        return node;
    }

    public static Node insert(Node root, int key) {
        root = insert0(root, key);
        //根结点始终保持黑色
        root.color = BLACK;
        return root;
    }

    private static Node insert0(Node root, int key) {
        if (root == NIL) return createNode(key);
        if (root.key == key) return root;
        if (key < root.key) {
            root.leftChild = insert0(root.leftChild, key);
        } else {
            root.rightChild = insert0(root.rightChild, key);
        }
        //回溯过程中进行红黑树的插入调整
        return insertMaintain(root);
    }

    //红黑树的插入调整，root为祖父节点
    public static Node insertMaintain(Node root) {
        //父节点和叔叔节点都不是红色，满足红黑树的性质，直接返回不用调整
        if (!hasRedChild(root)) return root;
        //父节点和叔叔节点都是红色
        if (root.leftChild.color == RED && root.rightChild.color == RED) {
            //祖父节点变为红色，父节点和叔叔节点变为黑色
            root.color = RED;
            root.leftChild.color = root.rightChild.color = BLACK;
            return root;
        }
        //父节点是红色，叔叔节点是黑色或者NIL节点
        if (root.leftChild.color == RED && hasRedChild(root.leftChild)) {
            //新节点在父节点的右子树上，先对父节点进行左旋，再对祖父节点进行右旋，可以红色上浮（祖父节点变为红色，父节点和叔叔节点变为黑色），也可以红色下沉（祖父节点变为黑色，父节点和叔叔节点变为红色）
            if (root.leftChild.rightChild.color == RED) {
                root.leftChild = leftRotate(root.leftChild);
            }
            //对祖父节点进行大右旋
            root = rightRotate(root);
        } else if (root.rightChild.color == RED && hasRedChild(root.rightChild)) {
            //新节点在父节点的左子树上，先对父节点进行右旋，再对祖父节点进行左旋
            if (root.rightChild.leftChild.color == RED) {
                root.rightChild = rightRotate(root.rightChild);
            }
            root = leftRotate(root);
        } else {
            //没有发生冲突
            return root;
        }
        //祖父节点变为红色，父节点和叔叔节点变为黑色
        root.color = RED;
        root.leftChild.color = root.rightChild.color = BLACK;
        return root;
    }

    public static Node delete(Node root, int key) {
        root = delete0(root, key);
        root.color = BLACK;
        return root;
    }

    @SuppressWarnings("UnusedAssignment")
    private static Node delete0(Node root, int key) {
        //该树中没有找到需要删除的结点
        if (root == NIL) return NIL;
        if (key < root.key) {
            //被删除节点在左子树，从左子树进行查找删除
            root.leftChild = delete0(root.leftChild, key);
        } else if (key > root.key) {
            root.rightChild = delete0(root.rightChild, key);
        } else if (root.leftChild == NIL || root.rightChild == NIL) {
            //被删除节点root的度为1和0，temp指向唯一子节点，没有唯一子节点则指向NIL结点
            Node temp = root.leftChild != NIL ? root.leftChild : root.rightChild;
            temp.color = root.color;
            root = null;
            return temp;
        } else {
            //被删除结点的度为2，temp指向被删除结点的前驱
            Node temp = predecessor(root);
            //转换为删除temp结点
            root.key = temp.key;
            root.leftChild = delete0(root.leftChild, temp.key);
        }
        //平衡红黑树
        return deleteMaintain(root);
    }

    //https://www.jianshu.com/p/0a3fe30e7a25
    //删除调整主要是为了消去双黑结点，root为父节点
    public static Node deleteMaintain(Node root) {
        //没有双黑结点，也就是没有冲突，不需要进行调整
        if (root.leftChild.color != DOUBLE_BLACK && root.rightChild.color != DOUBLE_BLACK) return root;
        //兄弟结点是红色
        if (hasRedChild(root)) {
            //双黑结点的兄弟结点为红色，对父节点（原根结点）变红进行旋转，并将新根结点变为黑色（交换原根结点和现根结点的颜色）
            root.color = RED;
            if (root.leftChild.color == RED) {
                //兄弟结点为红色且在双黑结点的左侧，跟结点变为红色并进行右旋，新根结点变为黑色
                root = rightRotate(root);
                root.rightChild = deleteMaintain(root.rightChild);
            } else {
                //兄弟结点为红色且在双黑结点的右侧，根结点变为红色并进行左旋，新根结点变为黑色
                root = leftRotate(root);
                root.leftChild = deleteMaintain(root.leftChild);
            }
            root.color = BLACK;
            return root;
        }
        //到这里兄弟结点全是黑色，如果兄弟结点没有红色子节点，则父节点黑色加1，双黑结点和兄弟结点黑色减1
        if ((root.leftChild.color == DOUBLE_BLACK && !hasRedChild(root.rightChild)) || (root.rightChild.color == DOUBLE_BLACK && !hasRedChild(root.leftChild))) {
            root.leftChild.color--;
            root.rightChild.color--;
            root.color++;
            return root;
        }
        if (root.leftChild.color == DOUBLE_BLACK) {
            //左子结点是双黑，如果其兄弟结点（右子节点）的左子节点为红色（RL），先对兄弟结点进行小右旋，并将新兄弟结点和原兄弟结点的颜色对换，再对父节点进行大左旋
            if (root.rightChild.rightChild.color != RED) {
                root.rightChild.color = RED;
                root.rightChild = rightRotate(root.rightChild);
                root.rightChild.color = BLACK;
            }
            //对父节点进行大左旋，新根结点颜色变为原根结点颜色，并将其两个子节点变为黑色
            root = leftRotate(root);
            root.color = root.leftChild.color;
        } else {
            //右子节点是双黑，如果其兄弟结点（左子节点）的右子节点为红色（LR），先对兄弟结点进行小左旋，并将新兄弟结点和元兄弟结点的颜色对换，再对父节点进行大右旋
            if (root.leftChild.leftChild.color != RED) {
                root.leftChild.color = RED;
                root.leftChild = leftRotate(root.leftChild);
                root.leftChild.color = BLACK;
            }
            //对父节点进行大右旋，新根结点颜色变为原根结点颜色，并将其两个子节点变为黑色
            root = rightRotate(root);
            root.color = root.rightChild.color;
        }
        //两个子节点变为黑色
        root.leftChild.color = root.rightChild.color = BLACK;
        return root;
    }

    //中序的前驱结点
    public static Node predecessor(Node root) {
        Node temp = root.leftChild;
        while (temp.rightChild != NIL) temp = temp.rightChild;
        return temp;
    }

    public static void main(String[] args) {
        Node root = NIL;
        Scanner scanner = new Scanner(System.in);
        System.out.println("1、添加结点");
        System.out.println("2、删除节点");
        System.out.println("-1、退出");
        int op, val;
        while ((op = scanner.nextInt()) != -1) {
            val = scanner.nextInt();
            switch (op) {
                case 1: root = insert(root, val); break;
                case 2: root = delete(root, val); break;
            }
            output(root);
            System.out.println("------------------------------");
        }
    }

    private static Node rightRotate(Node root) {
        Node temp = root.leftChild;
        root.leftChild = temp.rightChild;
        temp.rightChild = root;
        return temp;
    }

    private static Node leftRotate(Node root) {
        Node temp = root.rightChild;
        root.rightChild = temp.leftChild;
        temp.leftChild = root;
        return temp;
    }

    private static boolean hasRedChild(Node root) {
        return root.rightChild.color == RED || root.leftChild.color == RED;
    }

    private static Node initNilNode() {
        Node nil = new Node();
        nil.key = 0;
        nil.color = BLACK;
        nil.leftChild = nil.rightChild = NIL;
        return nil;
    }

    public static void output(Node root) {
        if (root == NIL) return;
        System.out.printf("(color: %s, value: %d, left: %d, right: %d)\n", root.color == 0 ? "红色" : "黑色", root.key, root.leftChild.key, root.rightChild.key);
        output(root.leftChild);
        output(root.rightChild);
    }
}
